/*
 * @lc app=leetcode id=139 lang=cpp
 *
 * [139] Word Break
 */
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int len = s.size();
        vector<bool> memo(len+1);
        memo[0] = true;

        for (int i=0; i<=len; i++) {
            if (i == 0 || memo[i-1]) {
                for (auto w : wordDict) {
                    int wlen = w.size();
                    if (i-1+wlen <= len) {
                        if (strncmp(w.data(), s.data()+i-1, wlen) == 0) {
                            memo[i+wlen-1] = true;
                        }
                    }
                }
            }
        }
        return memo[len];
    }
};

